本场链接:Codeforces Round #658
#A. Common Subsequence
A题太水了,不提.但是不知道为什么有人fst了这个题,等之后过来修一下.
#B. Sequential Nim
题目大意:有堆石子,每堆的数量是.两个人轮流玩这个游戏,每次可以从最左边的非空石堆里取出任意多个的石子.不能操作的人输,问是否先手必胜.
数据范围:
这是一个很显然的博弈论模型,拿走最后一堆的人胜利,即整个游戏的结果与最后一堆无关.手玩几个样例之后可以发现序列里如果有就会使情况变得不比较难缠,考虑简化一点的情况:除了最后一堆之前所有的石子都没有个的.可以发现在这种情况下先手是一定必胜的,考虑加入的影响:在看了样例之后可以很快的知道:的数量是与结果无关的,答案应该和是有关的,但不是数量问题.联想之前没有的游戏过程:每次都是让先手的人拿石子出现一个的局面,使第二个人只能选个石子,可以想到关键点就是:谁拿到了,或者可能是谁先拿到了非的数.推理之后可以发现答案是后者,具体来说,游戏过程里谁先碰到了一个非的数,谁就有主导权,一是把当前的数全部掏空,二是把当前的数变成一个,不管怎样,主导权都在先拿到非的人手上,最终一定是必胜的.
综上,结论:先拿到不是的人胜利.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int win = 1;
int n;scanf("%d",&n);
vector<int> a(n + 17,0);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int i = 1;
while(a[i] == 1)
{
if(i == n) break;
win ^= 1;
++i;
}
if(!win) puts("Second");
else puts("First");
}
return 0;
}
#C. Prefix Flip
题目大意:给定两个二进制字符串和,里面只有或两种元素.规定一种操作:选择里的一个前缀,先反转整个前缀里的所有状态(即到,反之亦然),再反转整个前缀字符串.现要使变成,求操作次数和具体方案.
#C1
数据范围:
这个子问题中,操作次数不得大于
这题乍看上去很牛逼,正面突破看起来没什么性质,逆向考虑也是一样.不过这题规定了说操作不得多于次,也就是说对于每一位来说,操作都不得多于次,即是上界.如果能想办法找出一种,对每个位置来说,如果他需要修改,就最多只会用次的方法,就可以通过本题了.
前面也说了,直接想要构造到的操作方案是很困难的,所以考虑对每一个不同的位置,从前往后考虑,我们要的就是,只改变当前这个位置的状态,而不修改前面的.比较容易想到如下的做法:每次先转一次当前这个位置的前缀,再转一次第一位(现在的第一位就是之前的最后一位),再转一次这个位置对应的前缀,就可以做到:不修改这个位置之前的内容,而把当前这个位置状态取反了.显然操作最多是次的,由此,可以轻松通过这个子问题.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
int n;cin >> n;
string a,b;cin >> a >> b;
vector<int> res;
for(int i = 0;i < n;++i)
{
if(a[i] != b[i])
{
res.push_back(i + 1);
res.push_back(1);
res.push_back(i + 1);
}
}
cout << res.size() << " ";for(auto& v : res) cout << v << " ";cout << endl;
}
return 0;
}
#C2
数据范围:
操作次数不得超过
首先是把扩大到了级,且旋转次数降低成了.
把数量降低了之后,又看起来非常牛逼了,不过既然这个题拆成了两半,所以上一题的方式绝对不是毫无价值的,可以借鉴过来与这个题一起思考.很显然,我们这里是要找两步操作,这两步操作的操作次数上界是,两步合在一起就不超过了.上一问必须要的原因是对每一个字符都进行操作,每个不同的要消耗个次数,产生了很多的冗余.解决的方向就是:整体考虑.
之前在里提到了说:想要直接把转成是十分困难的一件事,但是可以折中的考虑:有没有一种方式,能把和都变成一个相同的串,之后再把的操作部分和反转之后的的操作部分拼在一起,之后就是整个的操作方案了.第二步是比较好验证的,即反转之后的操作部分接过去肯定就是整个的操作方案,但是第一步比较困难,我们先梳理一下这个问题:找到一个特殊的串,使任意形态的和都能转移过来,并且一个串转到这种特殊串的代价的上界是小于等于的,这样,就可以解决了.
这个特殊的串,就是全部都是一个元素的串(这里构造串,另外一种也肯定是一样的),具体怎么使一个串变成一个串呢?只要把每一位和下一位不同的前缀转一次,就可以在上界不超过的情况下解决这个问题了,因为要的就是整个串都相同,把这一位转一下之后会使得这一位和下一位相同,并且依次进行的话,不会破坏前面已经排列好的串.不过特别注意一下,最后一个元素如果是的话,说明构造出来的串是串,还要额外的记录一次.最后,对和分别的做这个过程,并把的操作部分倒置一下,拼接起来就是最后的操作方案了,注意要先输出操作的步数.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
int n;cin >> n;
string a,b;cin >> a >> b;
if(a == b)
{
cout << 0 << endl;
continue;
}
vector<int> res;
for(int i = 0;i < n - 1;++i)
if(a[i] != a[i + 1])
res.push_back(i + 1);
if(a[n - 1] != '0') res.push_back(n);
vector<int> rev;
for(int i = 0;i < n - 1;++i)
if(b[i] != b[i + 1])
rev.push_back(i + 1);
if(b[n - 1] != '0') rev.push_back(n);
reverse(rev.begin(),rev.end());
for(auto& v : rev) res.push_back(v);
cout << res.size() << " ";
for(auto& v : res) cout << v << " ";cout << endl;
}
return 0;
}
#D. Unmerge
题目大意:规定对两个数组和的合并(merge)操作:
①若其中一个是空,则合并结果是另外一个非空数组
②若,则先去掉数组的首位元素,之后的合并结果为.
③若,则先去掉数组的首位元素,之后的合并结果为.
给定一个长度为的排列,问这个排列是否可以是某两个数组后的结果,,并且要求这两个数组的长度均是,输出是或否即可,不需要输出具体方案是怎样的.
数据范围:
这题乍看上去也很吊,是应该是一个的算法,但是这个也没得出太多的信息,可能就是一个,或者别的什么暴力遍历方法,没什么信息,还是去挖掘一下题目的性质.
从这个题目规定的操作来说,元素之间的关系,主要是大小关系,所以突破口应该是整个序列里的最值,这个最值可能跟的构造顺序有关,很可能就是破开问题的关键.
顺着这个想法想,先找到整个排列里的最大值,假设他的位置是,那么对于之前的所有元素,肯定都是比他小的,如果要进行比较的话,肯定是前面的所有元素分配在前面就好,对于之后的元素,他们也肯定是比这个最大元素要小的,所以这些元素必须要在这个最大值后面,否则会导致位置不对.也就是说,在不考虑具体和之前,我们可以可以把整个序列按这种方式,从最大值一直往前依次分成若干个块,这每个块之间都是独立的,
例如对这个排列:,分组之后就是,在这些组之间,找一个空隙放入一个板子,左边的部分和右边的部分就各自是一个和的方案了,注意不能从中间插入板子,也不能破坏原来的顺序.
现在这个问题就很明确了,就是有若干组元素,每次你可以选一组元素加入到正在构造的序列里去,每个元素只有选和不选两种情况,长度就是价值,长度也是体积,这就是一个背包模型,直接做就可以了.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
int f[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof f);
int n;scanf("%d",&n);
int mx = 0;
vector<int> _w;
for(int i = 0;i < 2 * n;++i)
{
int x;scanf("%d",&x);
if(x > mx)
{
_w.push_back(i);
mx = x;
}
}
_w.push_back(2 * n);
vector<int> w;
for(int i = 1;i < _w.size();++i) w.push_back(_w[i] - _w[i - 1]);
for(int i = 0;i < w.size();++i)
for(int j = n;j >= w[i];--j)
{
assert(w[i] >= 0);
f[j] = max(f[j],f[j - w[i]] + w[i]);
}
if(f[n] == n) puts("YES");
else puts("NO");
}
return 0;
}
E看起来太牛逼了,以后有空补吧